package com.hackerrank.contests.sep13.challenges.helpmike;

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		in.nextLine();
		for(int t = 0; t < T; t++) {
			long N = in.nextInt(), K = in.nextInt(), M = (2 * N - 1) / K, P = (N + 1) / K, C = 0;
			if(K % 2 == 0)
				C = M * ((M + 1) * K - 4) / 4;
			else
				C = (long)(M * ((M + 1) * K - 2) / 4.0 - (M / 2) / 2.0);
			if((N + 1) % K > 0)
				P++;
			long MC = (M * (M + 1) - P * (P - 1)) * K / 2 - (N + 1) * (M - P + 1);
			System.out.println(C - MC);
		}
	}
}
